iT邦幫忙

2021 iThome 鐵人賽

DAY 10
0
自我挑戰組

試煉之地 Leetcode 的挑戰系列 第 10

Leetcode 挑戰 Day 10 [171. Excel Sheet Column Number]

  • 分享至 

  • xImage
  •  

171. Excel Sheet Column Number


轉眼間,來到第十天了!今天這一題是一個和進位法換算相關的題目,會運用到一些ASCII的技巧,是相當有趣的一題,讓我們一起來看看吧!

題目


Given a string columnTitle that represents the column title as appear in an Excel sheet, return its corresponding column number.

For example:

A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28
...

Example 1:
Input: columnTitle = "A"
Output: 1

Example 2:
Input: columnTitle = "AB"
Output: 28

Example 3:
Input: columnTitle = "ZY"
Output: 701

Example 4:
Input: columnTitle = "FXSHRXW"
Output: 2147483647

這題的希望我們做的就是將26進位表示法的整數轉換成十進制,這邊的26進位比較特別的是前十個並不是用數字來表示,而是英文大寫字母A-Z,所以我們要回傳的就是相對應的整數。

ASCII and ForLoop


根據進位法的定義,我們可以得知十進位中的個位數是「在個位的數字10的0次方」、十位數是「十位數字10的1次方」依此類推,在二十六進制中也是相同的道理,個位數是「在個位的數字26的0次方」、十位數是「十位數字26的1次方」......,OK 那我們就可以用這個邏輯去做這一題。

可是重點來了,我們要怎麼知道A代表1,Z代表26,在起初我做這題的時候,是想到建立一個陣列或是HashMap,使其能夠一一對應,但後來突然想到,對電腦來說字母其實也是數字,也就是所謂的ASCII Code,那為何不用這個特性來達到A-Z => 1~26 的轉換,只要將A(ASCII中的65)轉換成整數並減去64,就變成1了,其餘的也一一對應,因此在我的算法中,的確就是使用到ASCII Code與for迴圈,按照定義將結果累加出來並回傳。

以下是python3的程式碼

class Solution:
    def titleToNumber(self, columnTitle: str) -> int:
        total = 0
        for i, v in enumerate(columnTitle[::-1]):
            total += (ord(v)-64) * (26 ** i)  # ASCII轉換成數字
        return total

以下是C++的程式碼

class Solution {
public:
    int titleToNumber(string columnTitle) {
        int count=0;
        int size = columnTitle.size();
        for(int i=0;i<size;i++){
            int o = columnTitle[size-(i+1)];
            count += (o-64) * (pow(26, i));
        }
        return count;
    }
};

以下也是C++的程式碼,但這個方法通過了優化迴圈進行方式,來達到不需要呼叫指數函式,會更節省空間與加強效率。

class Solution {
public:
    int colCharToInt( char ch ) {
        return ( ch - 'A' + 1 );
    }
    int titleToNumber(string columnTitle) {
        int currNum = 0;
        for( int i = 0; i < columnTitle.size(); i++ ) {
            int currVal = colCharToInt( columnTitle[i] );
            currNum = currNum * 26 + currVal;
        }
        return currNum;
    }
};

上一篇
Leetcode 挑戰 Day 09 [344. Reverse String]
下一篇
Leetcode 挑戰 Day 11 [242. Valid Anagram]
系列文
試煉之地 Leetcode 的挑戰19
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言